package bm6;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/7/20 18:19
 * BM6.判断链表中是否有环
 * https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&tqId=605&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 */
public class Solution {


    // 利用快慢指针判断链表是否有环
    public boolean hasCycle(ListNode head) {
        // 边界处理
        if (head == null || head.next == null) {
            return false;
        }
        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 快指针每次走两步, 慢指针每次走一步, 迭代判断是否会相遇
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true; // 相遇说明有环
            }
        }
        // 如果快指针正常遍历到链表的尾部, 说明无环
        return false;
    }

    private static class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
